In computer program execution systems, the choice of object model plays a central role in the design of any object-oriented language implementation. The object model dictates how objects will be represented in storage. It is widely recognized that the best object model will maximize the efficiency of frequent language operations while minimizing storage overhead.
A fundamental property of object-oriented languages is that the operations performed on an object depend upon the object's run-time type, rather than its compile-time type. Therefore, in any object model, each object must at a minimum contain a run-time type identifier, typically a pointer to a virtual method table.
Some modern object-oriented languages, like Java™, require additional per-object units of state to support richer functionality including garbage collection (see “Garbage Collection: Algorithms for Dynamic Memory Management” by R. Jones and R. Lins, John Wiley and Sons, 1996), hashing (see “Sorting and Searching”, Volume 3 of “The Art of Computer Programming” by D. Knuth, Addison-Wesley, 1973), and synchronization (see “The Java™ Language Specification” by J. Gosling, B. Joy, and G. Steele, Addison-Wesley, 1996). Generally, each extra unit of state imposes extra storage overhead for each object.
In view of the foregoing, the computer science literature has presented some object model implementation techniques designed to reduce the per-object storage overhead.
Some work has focused on reducing the per-object space overhead needed to represent an object's run-time type. This is covered in at least the following references: “Exploiting prolific types for memory management and optimizations”, Conference Record of the ACM Conference on Principles of Programming Languages, January 2002 by Y. Shuf et al.; “Space- and time-efficient implementation of the Java object model”, Proceedings of the European Conference on Object-Oriented Programming, June 2002 by D. Bacon et al.; “Data Size Optimizations for Java Programs”, by C. Scott Ananian and Martin Rinard, [http://]www.cag.lcs.mit.edu/˜cananian/Publications/sas02.pdf.
The initial Java virtual machine from Sun performed synchronization on objects via a hash table, itself synchronized with a global lock. The resulting system had poor synchronization performance, which turned out to be quite common in many Java programs.
A body of subsequent work improved the space and time overhead of the original Java object model with respect to locking. This is covered in at least the following references: “Monitors and exceptions: how to implement Java efficiently”, Concurrency: Practice and Experience 100, 11–13(1998), by A. Krall and M. Probst; “Thin locks: featherweight synchronization for Java”, Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998, by D. Bacon et al.; “Locking and unlocking mechanism for controlling concurrent access to objects”, U.S. Pat. No. 6,247,025, issued 12 Jun. 2001 to D. Bacon; “A study of locking objects with bimodal fields”, OOPSLA '99 Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications, Denver, Colo., October 1999, by T. Onodera and K. Kawachiya; “SableVM: A research framework for efficient execution of Java bytecode”, Proceedings of the Java Virtual Machine Research and Technology Symposium, Monterey, Calif., April 2001 by E. Gagnon and L. Hendren; “Lightweight monitor in Java virtual machine”, Proceedings of the Third Workshop on Interaction Between Compilers and Computer Architectures, San Jose, Calif., October 1998, by B. S. Yang et al.; “An efficient meta-lock for implementing ubiquitous synchronization”, OOPSLA '99 Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications, Denver, Colo., October 1999 by O. Agesen et al.; “Marmot: an optimizing compiler for Java”, Software—Practice and Experience, 30(3), 2000, by R. Fitzgerald et al.
All of the approaches just listed either sacrifice performance by imposing indirection into the locking sequence, or impose some per-object space overhead to represent locking state. Thus, it would be highly desirable to enable a system to reduce the per-object space overhead, while also minimizing the overhead due to indirection in the locking protocol.
Some other related work has focused on eliminating synchronization via compile-time analysis. This work is described in the following references: “Static analyses for eliminating unnecessary synchronization from Java programs”, Static Analysis: Sixth International Symposium, Venice, Italy, September 1999, by J. Aldrich et al.; “Comprehensive synchronization elimination for Java”, Tech. Report UW-CSE-00-10-01, Department of Computer Science, University of Washington, 2000, by J. Aldrich et al.; “Removing unnecessary synchronization in Java”, Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications, Denver, Colo., 1999, by J. Bogda and U. Holzle; “Effective synchronization removal for Java”, Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, Vancouver, British Columbia, June 2000, by E. Ruf.
Among the significant disadvantages of the efforts just listed is that they tend not to be capable of reducing object space overhead.
In view of the foregoing, a need has been recognized in connection with improving upon the shortcomings and disadvantages of conventional efforts.